{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TCP Congestion Control and Bufferbloat\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this assignment, you will create your own network simulation to investigate the dynamics of TCP and how seemingly minor configuration decisions made by network operators can have major performance effects. \n",
    "\n",
    "As discussed in lecture, TCP is a protocol for obtaining reliable transmission over an unreliable packet-switched network. Another important component of TCP is congestion control, i.e. limiting end host send rates to prevent network infrastructure from getting overwhelmed with traffic. \n",
    "\n",
    "However, networks can suffer congestion-related performance issues even when end hosts use TCP. One such issue, known as bufferbloat, can occur when packet buffers on routers and switches are too large. \n",
    "\n",
    "In this assignment, you will use Mininet, a useful tool for network experiments, to emulate a small network and collect various performance statistics relevant to TCP congestion control and bufferbloat. This will allow you to reason about the effects of TCP and router configuration on network performance.   \n",
    "\n",
    "**Put your name and netID in the cell below:**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Name:**\n",
    "\n",
    "**NetId:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Background\n",
    "\n",
    "#### TCP Congestion Window Size\n",
    "The TCP congestion window size parameter, typically styled \"cwnd,\" is maintained by the sender and determines how much traffic can be outstanding (sent but not acknowledged) at any time. There are many algorithms for controlling the value of cwnd during a TCP connection, all with the goal of maximizing the connection's throughput while preventing congestion. The additive increase and multiplicative decrease algorithm was discussed in lecture.\n",
    "\n",
    "#### Bufferbloat\n",
    "Bufferbloat is a phenomenon that happens when a switching device is configured to use excessively large buffers, which can in turn cause high latency and packet delay variation (jitter). This can happen even in a typical home network like the following:\n",
    "<img width=600 src=\"figures/home-network.png\">\n",
    "Here, the end host in the home network is connected to the home router. The home router is then connected, via cable or DSL, to a headend router run by the Internet service provider (ISP). By simulating and experimenting with a similar network in Mininet, you will see how bufferbloat causes poor performance.\n",
    "\n",
    "#### Mininet\n",
    "Mininet is a network emulator with which you can create a custom network of virtual hosts, switches, controllers, and links, all on a single computer. The virtual devices in the emulated network can run real programs; anything that can run on linux can run on a Mininet device too. This makes Mininet a valuable tool for fast and easy simulation of network protcols and measurements. This [Introduction to Mininet](https://github.com/mininet/mininet/wiki/Introduction-to-Mininet) is a useful guide for getting started with Mininet's Python API.  The [Mininet website](http://www.mininet.org) has additional resources if you are interested."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part A: Network Simulation & Measurement\n",
    "To start, you should first create the following network using Mininet's Python API, which emulates a typical home netowrk:\n",
    "<img width=450 src=\"figures/mininet-topo.png\">\n",
    "Here h1 is your home computer that has a fast connection (1Gb/s) to your home router. The home router has a slow uplink connection (1.5Mb/s). The round-trip propagation delay, or the minimum RTT between h1 and h2 is 20ms.  The router buffer (queue) size will be the parameterized independent variable in your simulation.\n",
    "\n",
    "To create a custom topology in Mininet, we extend the mininet.topo.Topo class. We have already added the switch (the router) to topology for you. You need to add h1, h2, and links with appropriate characteristics to create the setting specified in the image above.  The first few subsections of the [Working with Mininet](https://github.com/mininet/mininet/wiki/Introduction-to-Mininet#working) section of the Mininet guide describe how to add elements to a topology and set performance parameters. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mininet.topo import Topo\n",
    "\n",
    "class BBTopo(Topo):\n",
    "    \"Simple topology for bufferbloat experiment.\"\n",
    "\n",
    "    def __init__(self, queue_size):\n",
    "        super(BBTopo, self).__init__()\n",
    "        \n",
    "        # Create switch s0 (the router)\n",
    "        self.addSwitch('s0')\n",
    "        \n",
    "        # TODO: Create two hosts with names 'h1' and 'h2'\n",
    "\n",
    "        \n",
    "        # TODO: Add links with appropriate bandwidth, delay, and queue size parameters. \n",
    "        #       Set the router queue size using the queue_size argument\n",
    "        #       Set bandwidths/latencies using the bandwidths and minimum RTT given in the network diagram above\n",
    "        \n",
    "        \n",
    "        return"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we need a couple of helper functions to generate traffic between the two hosts. The following function starts a long-lived TCP flow which sends data from h1 to h2 using **iperf**. [Iperf](https://iperf.fr/) is \"a tool for active measurements of the maximum achievable bandwidth on IP networks.\"  You can think of this iperf traffic like a one-way video call. It continually attempts to send a high volume of traffic from the home computer h1 to the server h2. \n",
    "\n",
    "The following function receives one argument called `net`, which is an instance of mininet with a BBTopo topology that we have created above. We have written the part for the server (h2).  You need to complete the function to also start iperf on the client (h1). The iperf session should run for the number of seconds given in the `experiment_time` argument.\n",
    "\n",
    "You will need to use the `popen` function to run shell commands on a mininet host. The first argument to `popen` is a string command just like you would run in your shell. The second argument should be `shell=True`. You will need to look up the appropriate command line options to run iperf as a client for a given amount of time in the documentation here: [https://iperf.fr/iperf-doc.php#3doc](https://iperf.fr/iperf-doc.php#3doc). You will also need to include the IP address of h2 in your iperf command. This IP address can be accessed with the `h2.IP()` method.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def start_iperf(net, experiment_time):\n",
    "    # Start a TCP server on host 'h2' using perf. \n",
    "    # The -s parameter specifies server mode\n",
    "    # The -w 16m parameter ensures that the TCP flow is not receiver window limited (not necessary for client)\n",
    "    print \"Starting iperf server\"\n",
    "    h2 = net.get('h2')\n",
    "    server = h2.popen(\"iperf -s -w 16m\", shell=True)\n",
    "    \n",
    "    # TODO: Start an TCP client on host 'h1' using iperf. \n",
    "    #       Ensure that the client runs for experiment_time seconds\n",
    "    print \"Starting iperf client\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, you need to complete the following function that starts a back-to-back ping train from h1 to h2 to measure RTTs. A ping should be sent every 0.1 seconds. Results should be redirected from stdout to the `outfile` argument.\n",
    "\n",
    "As before, `net` is an instance of mininet with a BBTopo topology. As before, you will need to use `popen`.  The command argument to `popen` can redirect stdout using `>` just like a normal shell command.  Read the man page for `ping` for details on available command line arguments. Make sure the second argument to `popen` is `shell=True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def start_ping(net, outfile=\"pings.txt\"):\n",
    "    # TODO: Start a ping train from h1 to h2 with 0.1 seconds between pings, redirecting stdout to outfile\n",
    "    print \"Starting ping train\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we develop some helper functions to measure the congestion window of the TCP traffic. This will let us analyze at the dynamics of the TCP connections in the mininet network. The following functions are already complete."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "from subprocess import Popen\n",
    "import os\n",
    "\n",
    "def start_tcpprobe(outfile=\"cwnd.txt\"):\n",
    "    Popen(\"sudo cat /proc/net/tcpprobe > \" + outfile, shell=True)\n",
    "\n",
    "def stop_tcpprobe():\n",
    "    Popen(\"killall -9 cat\", shell=True).wait()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then create a helper function that monitors the queue length on a given interface. This will let us analyze how the number of packets in router buffer queues affects performance. This function is already complete."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "from multiprocessing import Process\n",
    "from monitor import monitor_qlen\n",
    "\n",
    "def start_qmon(iface, interval_sec=0.1, outfile=\"q.txt\"):\n",
    "    monitor = Process(target=monitor_qlen,\n",
    "                      args=(iface, interval_sec, outfile))\n",
    "    monitor.start()\n",
    "    return monitor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also need a helper function that starts a webserver on h1. This function is already complete."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import sleep\n",
    "\n",
    "def start_webserver(net):\n",
    "    h1 = net.get('h1')\n",
    "    proc = h1.popen(\"python http/webserver.py\", shell=True)\n",
    "    sleep(1)\n",
    "    return [proc]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we need a helper function that runs on h2, fetches the website from h1 every 3 seconds for `experiment_time`, and prints the average and standard deviation of the download times. This function is already complete"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import time\n",
    "from numpy import mean, std\n",
    "from time import sleep\n",
    "\n",
    "def fetch_webserver(net, experiment_time):\n",
    "    h2 = net.get('h2')\n",
    "    h1 = net.get('h1')\n",
    "    download_times = []\n",
    "    \n",
    "    start_time = time()\n",
    "    while True:\n",
    "        sleep(3)\n",
    "        now = time()\n",
    "        if now - start_time > experiment_time:\n",
    "            break\n",
    "        fetch = h2.popen(\"curl -o /dev/null -s -w %{time_total} \", h1.IP(), shell=True)\n",
    "        download_time, _ = fetch.communicate()\n",
    "        print \"Download time: {0}, {1:.1f}s left...\".format(download_time, experiment_time - (now-start_time))\n",
    "        download_times.append(float(download_time))\n",
    "        \n",
    "    average_time = mean(download_times)\n",
    "    std_time = std(download_times)\n",
    "    print \"\\nDownload Times: {}s average, {}s stddev\\n\".format(average_time, std_time)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we need to put together all the pieces to create the network, start all the traffic, and make the measurements. \n",
    "\n",
    "The following `bufferbloat()` function should:\n",
    "* create a `BBTopo` object\n",
    "* start the TCP and queue monitors\n",
    "* start a long-lived TCP flow using iperf\n",
    "* start the ping train\n",
    "* start the webserver\n",
    "* Periodically download the index.html web page from h1 and measure how long it takes to fetch it \n",
    "\n",
    "Note that the long lived flow, ping train, and webserver downloads should all be happening simultaneously. Once you have completed the assignment steps up until here, complete the sections marked `TODO` in the below `bufferbloat()` function. Each TODO section requires adding one line to call a function defined above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mininet.node import CPULimitedHost, OVSController\n",
    "from mininet.link import TCLink\n",
    "from mininet.net import Mininet\n",
    "from mininet.log import lg, info\n",
    "from mininet.util import dumpNodeConnections\n",
    "\n",
    "from time import time\n",
    "import os\n",
    "from subprocess import call\n",
    "\n",
    "def bufferbloat(queue_size, experiment_time, experiment_name):\n",
    "    # Don't forget to use the arguments!\n",
    "    \n",
    "    # Set the cwnd control algorithm to \"reno\" (half cwnd on 3 duplicate acks)\n",
    "    #    Modern Linux uses CUBIC-TCP by default that doesn't have the usual sawtooth\n",
    "    #    behaviour.  For those who are curious, replace reno with cubic\n",
    "    #    see what happens...\n",
    "    os.system(\"sysctl -w net.ipv4.tcp_congestion_control=reno\")\n",
    "    \n",
    "    # create the topology and network\n",
    "    topo = BBTopo(queue_size)\n",
    "    net = Mininet(topo=topo, host=CPULimitedHost, link=TCLink, \n",
    "                  controller= OVSController)\n",
    "    net.start()\n",
    "\n",
    "    # Print the network topology \n",
    "    dumpNodeConnections(net.hosts)\n",
    "    \n",
    "    # Performs a basic all pairs ping test to ensure the network set up properly\n",
    "    net.pingAll()\n",
    "    \n",
    "    # Start monitoring TCP cwnd size\n",
    "    outfile = \"{}_cwnd.txt\".format(experiment_name)\n",
    "    start_tcpprobe(outfile)\n",
    "\n",
    "    # TODO: Start monitoring the queue sizes with the start_qmon() function.\n",
    "    #       Fill in the iface argument with \"s0-eth2\" if the link from s0 to h2\n",
    "    #       is added second in BBTopo or \"s0-eth1\" if the link from s0 to h2\n",
    "    #       is added first in BBTopo. This is because we want to measure the \n",
    "    #       number of packets in the outgoing queue from s0 to h2. \n",
    "    outfile = \"{}_qsize.txt\".format(experiment_name)\n",
    "    qmon = start_qmon(iface=\"TODO\", outfile=outfile)\n",
    "\n",
    "    # TODO: Start the long lived TCP connections with the start_iperf() function\n",
    "\n",
    "    \n",
    "    # TODO: Start pings with the start_ping() function\n",
    "    outfile = \"{}_pings.txt\".format(experiment_name)\n",
    "\n",
    "    \n",
    "    # TODO: Start the webserver with the start_webserver() function\n",
    "\n",
    "    \n",
    "    # TODO: Measure and print website download times with the fetch_webserver() function\n",
    "\n",
    "    \n",
    "    # Stop probing \n",
    "    stop_tcpprobe()\n",
    "    qmon.terminate()\n",
    "    net.stop()\n",
    "    \n",
    "    # Ensure that all processes you create within Mininet are killed.\n",
    "    Popen(\"pgrep -f webserver.py | xargs kill -9\", shell=True).wait()\n",
    "    call([\"mn\", \"-c\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have completed all the steps above, use the `bufferbloat()` function to run the experiment twice, once with queue size of a 20 packets and then queue size of 100 packets. Make sure to run the experiments long enough to see the dynamics of TCP, like the sawtooth behavior of cwnd, in your results (300 seconds should be good).  Choose `experiment_name` arguments that reflect the queue size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from subprocess import call\n",
    "call([\"mn\", \"-c\"])\n",
    "\n",
    "# TODO: call the bufferbloat function twice, once with queue size of 20 packets and once with a queue size of 100.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part B: Plotting Results\n",
    "\n",
    "In this part of the assignment, you will analyze your measurements by plotting the variations in congestion window, queue length, and ping RTT versus time. We have provided plotting functions for each of these measurements, which are called in the following already complete `plot_measurements()` function. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "from plot_cwnd import plot_congestion_window\n",
    "from plot_qsize import plot_queue_length\n",
    "from plot_ping import plot_ping_rtt\n",
    "\n",
    "def plot_measurements(experiment_name_list, cwnd_histogram=False):\n",
    "    \n",
    "    # plot the congestion window over time\n",
    "    for name in experiment_name_list:\n",
    "        cwnd_file = \"{}_cwnd.txt\".format(name)\n",
    "        plot_congestion_window(cwnd_file, histogram=cwnd_histogram)\n",
    "    \n",
    "    # plot the queue size over time\n",
    "    for name in experiment_name_list:\n",
    "        qsize_file = \"{}_qsize.txt\".format(name)\n",
    "        plot_queue_length(qsize_file)\n",
    "    \n",
    "    # plot the ping RTT over time\n",
    "    for name in experiment_name_list:\n",
    "        ping_file = \"{}_pings.txt\".format(name)\n",
    "        plot_ping_rtt(ping_file)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you need to call the `plot_measurements` function such that the `experiment_name_list` argument is list of the `experiment_name` arguments you used to run `bufferbloat()` above.  This should generate 6 plots with the results of the experiments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "#TODO: Call plot_measurements() to plot your results\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part C: Analysis\n",
    "\n",
    "In this part of the assignment, you will answer some questions about TCP and bufferbloat using your simulations and the plots from the previous section.  This questions are intentionally open-ended and many have multiple correct answers.  There is no required answer length, but attempt to be both thorough and concise.  1-2 sentences is probably too short. More than 2-3 paragraphs is probably too long. \n",
    "\n",
    "Take some time first to think about the simulation you just performed. The simulation was set up like a home network with a home computer connected to a remote server through a router. The link from the router to the server had much lower bandwidth than the link from the home computer to the router. The independent variable in the simulation was the maximum length of the buffer of packets waiting to be sent from the router to the server. \n",
    "\n",
    "There were 3 sources of traffic:\n",
    "1. A long-lasting TCP session (creating using iperf) sending a high volume of traffic from the home computer to the server.\n",
    "2. Regularly spaced pings and ping replies to and from the home computer and the server\n",
    "3. Regularly spaced attempts to download a website (using HTTP over TCP) from the home computer to the server.\n",
    "\n",
    "As you (hopefully) discovered through the experiment, increasing the length of the packet buffer on the router significantly reduced performance by both ping RTT and HTTP download rate metrics. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q1.\n",
    "What computer networks other than a home network might have a configuration like the one you simulated?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A1.\n",
    "*TODO: your answer here.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q2.\n",
    "Write a symbolic equation to describe the relation between RTT and queue size. \n",
    "\n",
    "The symbolic equation should be generalized to any queue size. Basically, consider a snapshot of a system at one point of time, and use queue size and link delays parametrically to compute the RTT\n",
    "\n",
    "An example (incorrect) symbolic equation: \n",
    "$$RTT = kq^2$$\n",
    "where $k$ is a constant factor and $q$ is the number of packets in the queue. Your equation is not limited to $k$ and $q$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A2.\n",
    "*TODO: your answer here. Use single dollar signs for inline latex math formatting and double dollar signs for block latex math formatting.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q3.  \n",
    "Describe in technical terms why increasing buffer size reduces performance (RTTs and webpage download times), causing the bufferbloat effect.  Be sure to explicitly reference the plots you generated and the relationship between TCP congestion control and buffer size. *This is the most important question and will be weighted correspondingly more.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A3.\n",
    "*TODO: your answer here.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q4. \n",
    "Re-describe the cause of the bufferbloat effect using a non-technical analogy to something other than computer networking.  It is important to be able to describe technical content such that a layperson can understand, and generating analogies often helps your own reasoning. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A4.\n",
    "*TODO: your answer here.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q5. \n",
    "Is the bufferbloat effect specific to the type of network, traffic, and/or TCP congestion control algorithm we simulated, or is it a general phenomenon?\n",
    "\n",
    "Are there any times when increasing router buffer size would improve performance? If so, give an example.  If not, explain why not. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A5.\n",
    "*TODO: your answer here.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q6.\n",
    "Identify and describe a way to mitigate the bufferbloat problem without reducing buffer sizes.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A6.\n",
    "*TODO: your answer here.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Submission \n",
    "\n",
    "**Remember to \"Save and Checkpoint\" (from the \"File\" menu above) before you leave the notebook or close your tab.**\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
